// https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

// 算法思路总结：
// 1. 二分查找寻找旋转排序数组中的最小值
// 2. 通过与首元素比较判断中点所在区间
// 3. 根据中点值调整搜索区间边界
// 4. 返回右边界位置的最小值元素
// 5. 时间复杂度：O(log n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int findMin(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 1) return nums[0];
        if (nums[m - 1] > nums[0]) return nums[0];

        int l = -1, r = m;
        int key = nums[0];

        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] >= key)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        return nums[r];
    }
};

int main()
{
    vector<int> nums1 = {3,4,5,1,2}, nums2 = {11,13,15,17};
    Solution sol;

    cout << sol.findMin(nums1) << endl;
    cout << sol.findMin(nums2) << endl;

    return 0;
}